// 法一：暴力动态规划，O（N^3），TLE
class Solution {
public:
    bool isPalin(string s) {
        int l = 0;
        int r = s.length() - 1;
        while (l < r) {
            if (s[l] != s[r]) return false;
            ++l;
            --r;
        }
        return true;
    }
    int minCut(string s) {
        int len = s.length();
        vector<int> cuts(len, INT_MAX);
        for (int i = 0; i < len; ++i) {
            if(isPalin(s.substr(0, i + 1))) cuts[i] = 0;
        }
        for (int i = 1; i < len; ++i) {
            for (int j = 0; j < i; ++j) {
                if (isPalin(s.substr(j + 1, i - j)) && cuts[j] != INT_MAX) {
                    cuts[i] = min(cuts[i], cuts[j] + 1);
                }
            }
        }
        return cuts.back();
    }
};


// 法二：如果想要是 O(n^2) 的时间复杂度 (n 是 s 的长度)，需要事先求出来回文串信息，在状态转移时可以 O(1) 地知道一段子串是否回文。
class Solution {
public:
    int minCut(string s) {
        int len = s.length();
        vector<vector<bool>> isPalin(len, vector<bool>(len, true));
        for (int i = len - 1; i >= 0; --i) { // 注意计算方向
            for (int j = i + 1; j < len; ++j) {
                isPalin[i][j] = (s[i] == s[j]) && isPalin[i + 1][j - 1];
            }
        }
        vector<int> cuts(len, INT_MAX);
        for (int i = 0; i < len; ++i) {
            if(isPalin[0][i]) cuts[i] = 0;
        }
        for (int i = 1; i < len; ++i) {
            for (int j = 0; j < i; ++j) {
                if (isPalin[j + 1][i] && cuts[j] != INT_MAX) {
                    cuts[i] = min(cuts[i], cuts[j] + 1);
                }
            }
        }
        return cuts.back();
    }
};



// old
// https://www.lintcode.com/problem/palindrome-partitioning-ii/my-submissions

class Solution {
public:
    /**
     * @param s: A string
     * @return: An integer
     */
    // 法一：O（N^3）
    // bool judge(string s)
    // {
    //     int len = s.length();
    //     int i = 0;
    //     int j = len - 1;
    //     while (i < j)
    //     {
    //         if (s[i] != s[j])
    //             return false;
    //         i++;
    //         j--;
    //     }
    //     return true;
    // }
    // int minCut(string &s) {
    //     int len = s.length();
    //     vector<int> cuts(len + 1, INT_MAX);
    //     cuts[0] = -1;
    //     for (int i = 1; i < len + 1; ++i)
    //     {
    //         for (int j = 0; j < i; ++j)
    //         {
    //             if (judge(s.substr(j, i - j)) && cuts[j] != INT_MAX)
    //             {
    //                 cuts[i] = min(cuts[i], cuts[j] + 1);
    //             }
    //         }
    //     }
    //     return cuts.back();
    // }
    
    // 法二：如果想要是 O(n^2) 的时间复杂度 (n 是 s 的长度), 需要事先求出来回文串信息, 在状态转移时可以 O(1) 地知道一段子串是否回文的.
    
    int minCut(string &s)
    {
        int len = s.length();
        vector<vector<bool>> isPal(len, vector<bool>(len, false));
        int mid = 0, i = 0, j = 0;
        for (; i < len; ++i)
        {
            for (j = i; j < len; ++j)
                isPal[i][j] = false;
        }
        for (int mid = 0; mid < len; ++mid)
        {
            i = j = mid;
            while (i >= 0 && j < len && s[i] == s[j])
            {
                isPal[i][j] = true;
                i--;
                j++;
            }
            
            i = mid - 1;
            j = mid;
            while (i >= 0 && j < len && s[i] == s[j])
            {
                isPal[i][j] = true;
                i--;
                j++;
            }
        }
        vector<int> cuts(len + 1, INT_MAX); //最少可以划分多少段
        cuts[0] = 0;
        for (i = 1; i < len + 1; ++i)
        {
            for (j = 0; j < i; ++j)
            {
                if (isPal[j][i - 1])
                {
                    cuts[i] = min(cuts[i], cuts[j] + 1);
                }
            }
        }
        return cuts[len] - 1; 
    }
};